package LearnDataStructure.d_图结构.a_深度优先搜索DFS;

import java.util.Scanner;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-14 19:34
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.例题
 */
/*给定一个方阵，定义连通：上下左右相邻，并且值相同。
可以想象成一张地图，不同的区域被涂以不同颜色。
输入：
整数N, (N<50)表示矩阵的行列数
接下来N行，每行N个字符，代表方阵中的元素
接下来一个整数M，(M<1000)表示询问数
接下来M行，每行代表一个询问，
格式为4个整数，y1,x1,y2,x2，
表示询问(第y1行,第x1列) 与 (第y2行,第x2列) 是否连通。
连通输出true，否则false

例如：
10
0010000000
0011100000
0000111110
0001100010
1111010010
0000010010
0000010011
0111111000
0000010000
0000000000
3
0 0 9 9
0 2 6 8
4 4 4 6

程序应该输出：
false
true
true
*/
public class a_四连通byDFSand回溯 {
    public static void main(String[] args) {
        a_四连通byDFSand回溯 test = new a_四连通byDFSand回溯();
        test.useCheck();
    }

    public void useCheck() {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        char[][] graph = new char[N][N];
        for (int i = 0; i < N; i++) {
            graph[i] = scanner.next().toCharArray();
        }
        int M = scanner.nextInt();
        int[][] query = new int[M][4];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < 4; j++) {
                query[i][j] = scanner.nextInt();
            }
        }
        for (int i = 0; i < M; i++) {
            boolean ok = check(graph, new int[N][N], query[i]);
            System.out.println(ok);
        }
    }

    /**
     * 递归+回溯
     * 有回溯的递归，你如果模拟一遍
     * 肯定的，你会发现某一边递归中走过的格子，下一次递归时候又会走一遍
     * 这种浪费时间的情况是不可避免的
     * 所以递归+回溯的算法都不怎么高效
     * @param graph
     * @param label
     * @param coordinates
     * @return
     */
    private boolean check(char[][] graph, int[][] label, int[] coordinates) {
        int x1 = coordinates[0];
        int y1 = coordinates[1];
        int x2 = coordinates[2];
        int y2 = coordinates[3];

        if (x1 == x2 && y1 == y2) {//找到的情况的递归出口
            return true;
        }

        int value = graph[x1][y1];
        boolean f1 = false;
        boolean f2 = false;
        boolean f3 = false;
        boolean f4 = false;

        if (x1 - 1 >= 0 && label[x1 - 1][y1] == 0 && graph[x1 - 1][y1] == value) {//左
            label[x1-1][y1] = 1;
            coordinates[0] = x1 - 1;
            f1 = check(graph,label,coordinates);

            //回溯
            label[x1 - 1][y1] = 0;
            coordinates[0] = x1;
        }

        if (x1 + 1 < graph.length && label[x1 + 1][y1] == 0 && graph[x1 + 1][y1] == value) {//右
            label[x1+1][y1] = 1;
            coordinates[0] = x1 + 1;
            f2 = check(graph,label,coordinates);

            //回溯
            label[x1 + 1][y1] = 0;
            coordinates[0] = x1;
        }

        if (y1 - 1 >= 0 && label[x1][y1 - 1] == 0 && graph[x1][y1 - 1] == value) {//上
            label[x1][y1-1] = 1;
            coordinates[1] = y1 - 1;
            f3 = check(graph,label,coordinates);

            //回溯
            label[x1][y1 - 1] = 0;
            coordinates[1] = y1;
        }

        if (y1 + 1 < graph.length && label[x1][y1 + 1] == 0 && graph[x1][y1 + 1] == value) {//下
            label[x1][y1+1] = 1;
            coordinates[1] = y1 + 1;
            f4 = check(graph,label,coordinates);

            //回溯
            label[x1][y1 + 1] = 0;
            coordinates[1] = y1;
        }
        return f1 || f2 || f3 || f4;//巡查一遍后递归出口
    }
}
